#include<stdio.h> 
#include<vector>
#include<iostream>

#include <map>

using namespace std;

class Solution {
public:
    // 数据成员
    vector<int> rtn;
    vector<int> input;
    int target;

    // 暴力枚举
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> tmp = vector<int>(nums);

        if (nums.size() < 2 || nums.size() > 10000) {
            cout << "length is invalid." << endl;
            return rtn;
        }

        if (target < -1000000000 || target > 1000000000) {
            cout << "target is invalid." << endl;
            return rtn;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < -1000000000 || nums[i] > 1000000000) {
                cout << nums[i] << "is invalid." << endl;
                return rtn;
            }
            for (int j = i+1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    rtn.push_back(i);
                    rtn.push_back(j);
                }
            }
        }
        return rtn;
    }

    // 哈希表
    vector<int> twoSum_hash(vector<int>& nums, int target) {
        map<int, int> hashTable;
        for (int i = 0; i < nums.size(); ++i)
        {
            auto it = hashTable.find(target-nums[i]);
            if (it != hashTable.end()) {
                return {it->second, i};
            }
            hashTable[nums[i]] = i;
        }

        return {};
    }

};

int main(void)
{
    Solution newSolution = Solution();
    // for (int i = 1; i < 10000; ++i)
    // {
    //     newSolution.input.push_back(i);
    //     // cout << newSolution.input[i] << endl;
    // }
    // newSolution.input.push_back(2);
    // newSolution.input.push_back(7);
    // newSolution.input.push_back(11);
    // newSolution.input.push_back(15);
    // newSolution.input.push_back(3);
    // newSolution.input.push_back(6);
    // newSolution.input.push_back(8);
    // newSolution.input.push_back(9);

    newSolution.input.push_back(2);
    newSolution.input.push_back(3);
    newSolution.input.push_back(6);
    newSolution.input.push_back(7);
    newSolution.input.push_back(8);
    newSolution.input.push_back(9);
    newSolution.input.push_back(11);
    newSolution.input.push_back(15);

    newSolution.target = 20;
    
    vector<int> test = newSolution.twoSum_hash(newSolution.input, newSolution.target);

    // if (!newSolution.rtn.empty()) {
    //     cout << "[" << newSolution.rtn[0] << ", " << newSolution.rtn[1] << "]" << endl;
    // }else {
    //     cout << "result is error." << endl;
    // }
    
    if (!test.empty()) {
        cout << "[" << test[0] << ", " << test[1] << "]" << endl;
    }else {
        cout << "result is error." << endl;
    }

    return 0;
}

// g++ -g -Wall -std=c++11 two-sum.cpp